'''
https://leetcode.cn/problems/max-area-of-island/description/?envType=study-plan-v2&envId=graph-theory
'''
from typing import List


class UF:
    def __init__(self, n):
        self.father = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if x != self.father[x]:
            self.father[x] = self.find(self.father[x])
        return self.father[x]

    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx != fy:
            self.father[fy] = fx
            self.size[fx] += self.size[fy]


class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        idx = lambda i, j: i * n + j
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        uf = UF(n * m)
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    for ti, tj in directions:
                        ti, tj = i + ti, j + tj
                        if 0 <= ti < m and 0 <= tj < n and grid[ti][tj]:
                            uf.union(idx(i, j), idx(ti, tj))
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    res = max(res, uf.size[idx(i, j)])
        return res

    def maxAreaOfIsland2(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
                return 0
            grid[i][j] = 0
            res = 1
            for ti, tj in directions:
                ti, tj = i + ti, j + tj
                res += dfs(ti, tj)
            return res
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    res = max(res, dfs(i, j))
        return res


